1. Field of the Invention
The present invention relates to a methodology, and system for implementing the methodology, for performing an iterative scalar multiplication process utilizing the Takagi algorithm, the most-to-least binary algorithm, or the least-to-most binary algorithm, modified with either a simultaneous register access operation (SRA) or a general simultaneous register access operation (GSRA).
2. Description of the Related Art
The field of cryptography provides various methods of providing privacy and authentication for remote communications and data storage. Privacy is achieved through the encryption of data, commonly using the techniques of “symmetric cryptography” (so-called because the same mathematical key is used to encrypt and decrypt the data). Authenticity is achieved through the functions of user identification, data integrity, and message non-repudiation. These are best achieved via asymmetric (or public-key) cryptography.
In particular, public-key cryptography enables encrypted communication between users who have not previously established a shared secret key between themselves. This is most often accomplished using a combination of symmetric and asymmetric cryptography; i.e., public-key techniques are used to establish user identity and a common symmetric key, and a symmetric encryption algorithm is used for the encryption and decryption of the actual messages. The former operation is generally referred to as “key agreement”. Prior establishment is necessary in symmetric cryptography, which uses algorithms for which the same key is used to encrypt and decrypt a message. Public-key cryptography, in contrast, is based on key pairs. A key pair consists of a private key and a public key. As the names imply, the private key is kept private by its owner, while the public key is made public (and typically associated with its owner in an authenticated manner). In asymmetric encryption, the encryption step is performed using the public key, and decryption is performed using the private key. Thus, the encrypted message can be sent along an insecure channel with the assurance that only the intended recipient can decrypt it. The key agreement can be interactive (e.g., for encrypting a telephone conversation) or non-interactive (e.g., for electronic mail).
User identification is most easily achieved using what are generally referred to as “identification protocols”. A related technique, the use of digital signatures, provides data integrity and message non-repudiation in addition to user identification. The public key is used for encryption or signature verification of a given message, and the private key is used for decryption or signature generation of the given message.
The use of cryptographic key pairs was disclosed in U.S. Pat. No. 4,200,770, entitled “CRYPTOGRAPHIC APPARATUS AND METHOD”, which is herein incorporated by reference. U.S. Pat. No. 4,200,770 also disclosed the application of key pairs to the problem of key agreement over an insecure communication channel. The algorithms specified in this U.S. Pat. No. 4,200,770 rely, for their security, on the difficulty of the mathematical problem of finding a discrete logarithm.
In order to undermine the security of a discrete-logarithm based crypto-algorithm, an adversary must be able to perform the inverse of modular exponentiation (i.e., a discrete logarithm). There are mathematical methods for finding a discrete logarithm (e.g., the Number Field Sieve), but these algorithms cannot be performed in any reasonable time using sophisticated computers if certain conditions are met in the specification of the crypto-algorithm.
In particular, it is necessary that the numbers involved be large enough. The larger the numbers used, the more time and computing power are required to find the discrete logarithm and break the cryptograph. On the other hand, very large numbers lead to very long public keys and transmissions of cryptographic data. The use of very large numbers also requires large amounts of time and computational power in order to perform the crypto-algorithm. Thus, cryptographers seek new ways to minimize the size of the numbers involved, and the time and power required, in performing the encryption and/or authentication algorithms. The payoff for finding such a method is that cryptography can be performed faster, cheaper, and on devices that do not require large amounts of computational power (e.g., hand-held smart-cards).
A discrete-logarithm based crypto-algorithm can be performed in any mathematical setting in which certain algebraic rules hold true. In mathematical language, the setting must be a finite cyclic group. The choice of the group is critical in a cryptographic system. The discrete logarithm problem may be more difficult in one group than in another for which the numbers are of comparable size. The more difficult the discrete logarithm problem, the smaller the numbers that are required to implement the crypto-algorithm. Working with smaller numbers is easier and faster than working with larger numbers. Using small numbers allows the cryptographic system to be higher performing (i.e., faster) and requires less memory storage. Thus, by choosing the right kind of group, a user may be able to work with smaller numbers, make a faster cryptographic system, and get the same, or better, cryptographic strength than from another cryptographic system that uses larger numbers.
The groups referred to above come from a mathematical field generally referred to as “finite fields”. Methods of adapting discrete-logarithm based algorithms to the setting of elliptic curves are known. However, finding discrete logarithms in this type of group is particularly difficult. Thus, elliptic curve-based crypto-algorithms can be implemented using much smaller numbers than in a finite field setting of comparable cryptographic strength. Thus, the use of elliptic curve cryptography represents an improvement over finite field based public key cryptography.
In practice, an Elliptic Curve group over Fields F(p), denoted as E(p), is formed by choosing a pair of a and b coefficients, which are elements within F(p). The group consists of a finite set of points P(x,y), which satisfy the elliptic curve equation, given by:F(x,y)=y2−x3−ax−b=0,together with a point at infinity, O. The coordinates of the point, x and y, are elements of F(p) represented in N-bit strings. In the following discussion, a point is either written as a capital letter, e.g. P, or as a pair in terms of the affine coordinates, i.e. (x,y).
The Elliptic Curve Cryptosystem relies upon the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP) to provide its effectiveness as a cryptosystem. Using multiplicative notation, the problem can be described thusly: given points B and Q in the group, find a number k such that Bk=Q; where k is called the discrete logarithm of Q to the base B. Using additive notation, the problem becomes: given two points B and Q in the group, find a number k such that kB=Q.
In an Elliptic Curve Cryptosystem, the large integer k is kept private and is often referred to as the “secret key”. The point Q together with the base point B are made public and are referred to as the public key. Thus, the security of the system relies upon the difficulty of deriving the secret k, knowing the public points B and Q. The main factor that determines the security strength of such a system is the size of its underlying finite field. In a real cryptographic application, the underlying field is made so large that it is computationally infeasible to determine k in a straightforward way by computing all the multiples of B until Q is found.
The core of the elliptic curve geometric arithmetic is an operation called scalar multiplication, which computes kB by adding together k copies of the point B. The scalar multiplication is performed through a combination of point-doubling and point-addition operations. The point-addition operation adds two distinct points together and the point-doubling operation adds two copies of a point together. To compute, for example, B=(2*(2*(2B)))+3B=Q, it would take 3 point-doublings and 1 point-addition.
Addition of two points on an elliptic curve is calculated as follows: When a straight line is drawn through the two points, the straight line intersects the elliptic curve at a third point. The point symmetric to this third intersecting point with respect to the x-axis is defined as a point resulting from the addition.
Doubling a point on an elliptic curve is calculated as follows: When a tangent line is drawn at a point on an elliptic curve, the tangent line intersects the elliptic curve at another point. The point symmetric to this intersecting point with respect to the x-axis is defined as a point resulting from the doubling.
Table 1 illustrates the addition rules for adding two points (x1,y1) and (x2,y2), i.e.,(x3,y3)=(x1,y1)+(x2,y2).
TABLE 1Summary of Addition Rules: (x3, y3) = (x1, y1) + (x2, y2)Generalx3 = m2 − x2 − x1Equationsy3 = m (x3 − x1) + y1Point Addition  m  =                    y        2            -              y        1                            x        2            -              x        1             Point Doubling (x3, y3) = 2(x1, y1)  m  =                    3        ⁢                  x          1          2                    -      a              2      ⁢              y        1             (x2, y2) = −(x1, y1)(x3, y3) = (x1, y1) + (−(x1, y1)) = O(x2, y2) = O(x3, y3) = (x1, y1) + O = (x1, y1)
In elliptic curve encryption and decryption, the user begins with a message point (xm,ym), a base point (xB,yB), and a given key, k, and the cipher point (xC,yC) is obtained using the following equation:(xC,yC)=(xm,ym)+k(xB,yB)
There are two basics steps in the computation of the above equations. The first step is to find the scalar multiplication of the base point with the key, i.e. k(xB,yB). The resulting point is then added to the message point, (xm,ym) to obtain the cipher point.
At the receiver, the message point is recovered from the cipher point, which is usually transmitted to the receiver, along with the shared key and the base point:(xm,ym)=(xC,yC)−k(xB,yB).
The steps of elliptic curve symmetric cryptography can be summarized as follows:
First, both the sender and receiver must agree on:                1. A random number, k, that will be the shared secret key for communication, and,        2. A base point, P=(xB,yB).The sender follows the following encryption steps:        1. Embed a message bit string into the x coordinate of an elliptic curve point which is designated as the message point, (xm, ym);        2. The cipher point (xC, yC) is computed using (xc,yc)=(xm,ym)+k(xB,yB); and,        3. The appropriate bits of the x-coordinate and the sign bit of the y-coordinate of the cipher point (xC, yC) are sent to the receiving entity.        
At the receiver, the following steps are then performed:                1. Using the shared key, k, and the base point (xB, yB), the scalar multiplication (xBk, yBk)=k(xB, yB) is computed;        2. The message point (xm,ym) is computed using (xm,ym)=(xc,yc)+(−k(xB,yB)); and,        3. The secret messages bit string is recovered from xm.        
The steps of elliptic curve public key cryptography can be summarized as follows:
First, both the sender and receiver must agree on:
1. An elliptic curve; and,
2. A base point, P=(xB,yB).
At the sender, the following steps are followed:
1. Embed a message bit string into the x-coordinate of an elliptic curve point which is designated as the message point, (xm, ym);
2. Using the private key of the sending correspondent, kSPr, and the public key of the receiving correspondent, kRPr(xb, yb), compute the scalar multiplication (xbk, ybk)=kSPr (kRpr (xb, yb));
3. Compute a cipher point (xc, yc) using (xc, yc)=(xm, ym)+(xbk, ybk); and,
4. Send appropriate bits of the x-coordinate and the sign bit of the y-coordinate of the cipher point (xc, yc) to the receiving correspondent.
At the receiver, the following steps are then followed:
1. Using the private key of the receiving correspondent, kRPr, and the public key of the sending correspondent, kSPr(xb, yb), compute the scalar multiplication (xbk, ybk)=kRPr (kSPr (xb, yb));
2. Compute the message point (xm, ym) using (xm, ym)=(xc, yc)−(xbk, ybk); and,
3. Recover the message bit string from xm.
“Scalar multiplication” (SM) (or point multiplication) refers to computing the point KP=P P+P+ . . . P(sum taken K times) on the elliptic curve over a given finite field. The integer K is referred to as a “scalar” and the point P as the base point. However, adding the point P to itself K times is not an efficient way to compute scalar multiplication. More efficient methods are based on a sequence of addition (ADD) and doubling (DBL) operations. The doubling operation is simply adding the point to itself.
The computation of the point KP processed by scalar multiplication is performed using the binary expression of K represented by the equation:K=kn-12n-1+kn-22n-2+ . . . +k12+k0 where ki is the lth bit of the binary representation of K, and n is the total number of bits.
There are two common methods of calculating KP. First is the Least-to-Most (LM) algorithm, which starts from the least significant bit of K, and the Most-to-Least (ML) algorithm which starts from the most significant bit of K. The LM algorithm is given by:
INPUT    K, POUTPUT   KP1. Initialize Q[0] = O, Q[1] = P2. for i = 0 to n−13.   if k[i] == 1 then4.     Q[0] = ADD(Q[0],Q[1])5.   end if6.   Q[1] = DBL(Q[1])7. end for8. return Q[0];and, the ML algorithm is given by:
INPUT    K, POUTPUT   KP1. Initialize Q[0] = P2. for i = n−2 downto 03.   Q[0] = DBL(Q[0])4.   if k[i] == 1 then5.     Q[0] = ADD(Q[0],P)6.   end if7. end forreturn Q[0].
In the LM algorithm, Q[0] is initialized to the identity point O, and Q[1] to the base point P. If ki=1, the elliptic curve addition, ADD, is performed on the points Q[0] and Q[1] in step 4 and the result is stored in the point Q[0], otherwise (i.e. for ki=0) Q[0] remains unchanged. The elliptic curve doubling, DBL, is performed on the point Q[1] in Step 6, and the result is stored in the point Q[1]. This point doubling operation in step 6 is performed in all cases regardless of the scalar bit value.
The ML algorithm treats the bit string of K starting with the most significant bit first. Since the most significant bit is always 1, the ML algorithm starts from the next most bit, n−2, and initialize Q[0] to P. This kind of algorithms need only one variable, Q[0]. First, DBL operation is performed on Q[0] and the result is stored in Q[0] as shown in Step 3. This point doubling in Step 3 is performed regardless of the scalar bit value. If ki=1, ADD operation is performed on the point Q[0] and the base point P in step 5 and the result is stored in point Q[0], otherwise (i.e. for ki=0) Q[0] remains unchanged.
The difficulty in solving the elliptic curve discrete logarithm problem has been established theoretically. However, information associated with secret information such as the private key or the like may leak out in cryptographic processing in real-life situations. Thus, there has been proposed an attack method of so-called “power analysis”, in which the secret information is decrypted on the basis of the leaked information.
An attack method in which change in voltage is measured in cryptographic processing using secret information, such as the Data Encryption Standard (DES) or the like, so that the process of the cryptographic processing is obtained and the secret information is inferred on the basis of the obtained process is disclosed in P. Kocher, J. Jaffe and B. Jun, “Differential Power Analysis”, Advances in Cryptology: Proceedings of CRYPTO '99, LNCS 1666, Springer-Verlag, (1999) pp. 388-397. This attack method is commonly referred to as Differential Power Analysis (DPA).
As shown in the above LM and ML algorithms, performing the ADD operation is conditioned upon the key bit. If the scalar bit value is ONE, an ADD operation is performed, otherwise, an ADD operation is not performed. Therefore, a simple power analysis (i.e., simple side-channel analysis using power consumption as the side channel) will produce different power traces that distinguish between the existence of an ADD operation or not. This can reveal the bit values of the scalar.
One widely used approach to avoid this kind of leak is by J. Coron, published in “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems”, Cryptographic Hardware and Embedded Systems: Proceedings of CHES '99, LNCS 1717, Springer-Verlag, (1999) pp. 292-302. He suggests the performance of a dummy addition in the ML method when the processed bit is “0” so that each iteration appears as a doubling followed by an addition operation which is generally referred to as the “Double-and-ADD always” algorithm. Coron's algorithm is given by the following:
INPUT    K, POUTPUT   KP1. Initialize Q[2] = P2. for i = n−2 down to 03.   Q[0] = DBL(Q[2])4.   Q[1] = ADD(Q[0], P)5.   Q[2] = Q[ki]6. end for    return Q[2].
Similar to the LM algorithm, the Double-and-ADD always algorithm can be implemented as follows:
INPUT    K, POUTPUT   KP 1. Initialize Q[0] = P, Q[1] = P 2. for i = 1 to n−1 3.   Q[0] = DBL(Q[0]) 4.   Q[2] = ADD(Q[0], Q[1]) 5.    Q[1] = Q[1+ ki]   end for    return Q[1].
Another ML-type algorithm for preventing this type of information leak is disclosed in U.S. Published Patent Application No. 2003/0123656, entitled “ELLIPTIC CURVE CHRYPTOSYSTEM APPARATUS, STORAGE MEDIUM STORING ELLIPTIC CURVE CRYPTOSYSTEM PROGRAM, AND ELLIPTIC CURVE CRYPTOSYSTEM ARITHMATEC METHOD”. This algorithm uses extra ADD operations to assure that the sequence of DBL and ADD operations is carried out in each iteration. This algorithm, referred to as Takagi's algorithm, is given by:
INPUT    K, POUTPUT   KP 1. Initialize Q[0] = P, Q[1] = 2P 2. for i = n−2 down to 0 3.   Q[2] = DBL(Q[ki]) 4.   Q[1] = ADD(Q[0], Q[1]) 5.   Q[0] = Q[2− ki], 6.   Q[1] = Q[1+ ki] 7. end for   return Q[0]
However, even if an algorithm is protected against single power analysis, it may succumb to the more sophisticated differential power analysis (DPA). Assuming that the double-and-add always method is implemented with one of the previous algorithms (i.e., Coron's algorithm, the LM double-and-ADD always algorithm, or Takagi's algorithm), then we may represent the scalar value Kin binary as:K=kn-12n-1+kn-22n-2+ . . . +k12+k0,where ki is the lth bit of the binary representation of K, and n is the total number of bits. DPA is based on the assumption that an attacker already knows the highest bits, kn-1,kn-2 . . . kj+1, of K. Then, the attacker guesses that the next bit kj is equal to “1”, and then randomly chooses several points P1, . . . , Pt to compute:
            Q      r        =                  (                              ∑                          i              =              j                                      n              -              1                                ⁢                                    k              i                        ⁢                          2                              i                -                j                                                    )            ⁢              P        r              ,          ⁢            for      ⁢                          ⁢      1        ≤    r    ≤          t      .      
Based on statistical information of these points (i.e., Qr, 1≦r≦t), the attacker can decide whether his or her guess is correct or not. Once kj is known, the remaining bits, kj−1,kj−2 . . . k0, are recovered recursively, in the same way.
J. Coron, in “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems”, Cryptographic Hardware and Embedded Systems: Proceedings of CHES '99, LNCS 1717, Springer-Verlag, (1999) pp. 292-302, proposed the following randomization-based countermeasure steps, which are effective against differential power analysis attacks:
1. Randomizing the Base-Point P                a. Compute Q=kpas Q=(P+R)−kR for a random point R;        
2. Using Randomized Projective Coordinates:                a. For a random number r≠0, the projective coordinates, (X, Y, Z) and (rX, rY, rZ) represent the same point. So for a random number r, if P=(x0, y0), Q is computed as Q=k(rx0, ry0,:r); and,        
3. Randomizing the Scalar K                a. If n=ordE(P) denotes the order of PεE(F(p)), then Q is computed as Q=(k+r n)P for a random r. Alternatively, one can replace n by the order of the elliptic curve, #E(F(p)).        
These countermeasures can be used in combination with Coron's algorithm or Takagi's algorithm (both given above) to protect scalar multiplication computation against both simple power attacks and differential power analysis attacks.
The basic concept behind the “Address-Bit Attack” (ABA) is disclosed in Kouichi Itoh, Tetsuya Izu, and Masahiko Takenaka, “Address-Bit Differential Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA”, Cryptographic Hardware and Embedded Systems: Proceedings of CHES '2002, LNCS 2523, Springer-Verlag, (2002) pp. 129-143.
This attack is based on the correlation between bit values of the scalar and the location (address) of the variables used in a scalar multiplication algorithm. The countermeasures used to protect against simple power analysis and differential power analysis which are based on randomization of the base point or the projective coordinate do not provide countermeasure against address-bit analysis attacks. Therefore, these countermeasures do not remove the correlation between the bit values of a scalar and the location (address) of the variables used in a scalar multiplication algorithm.
Considering, for example, Takagi's algorithm, the variables' values can be randomized by randomizing the projective coordinates (or the base point) as shown in FIG. 5A. However, FIG. 5B shows that the location of input operand of the DBL operation (dotted line) and the data transfer from either Q[1] or Q[2] to Q[0] (solid line) are correlated to the bit value of the scalar. FIGS. 5A and 5B (and also steps 5 and 6 in Takagi's algorithm) show that, in Takagi's algorithm, the following data transfer is performed based on the bit value of the scalar:
            Q      ⁡              [        0        ]              =          {                                                  Q              ⁡                              [                2                ]                                                                                        k                i                            =              0                                                                          Q              ⁡                              [                1                ]                                                                                        k                i                            =              1                                          }                  Q      ⁡              [        1        ]              =          {                                                  Q              ⁡                              [                1                ]                                                                                        k                i                            =              0                                                                          Q              ⁡                              [                2                ]                                                                                        k                i                            =              1                                          }      
Similar correlation exits in Coron's algorithm (in step 5), in which Q[2] is loaded by either Q[0] or Q[1], based on the bit value of the scalar.
It should be noted that any algorithm where the location of the input operands or the location of the result is still dependent on the scalar bit values is vulnerable to ABA. Therefore, randomizing the base point or the projective coordinates as a countermeasure will not help in preventing this kind of attack because the locations of the input and/or output operands are still correlated to the scalar bits.
The process of randomizing the scalar value is also vulnerable to ABA. One might infer that leaking information about the bit values of the randomized scalar, and hence recovering the bit values of the randomized scalar, is acceptable since they do not represent the bit values of the actual scalar. However, the attacker can recover the correct bit values of the actual scalar from the recovered bits of the randomized scalar, as well as knowledge about the scalar randomization algorithm, which is usually based on redundant modulo representation.
Other scalar multiplication methods have been proposed. For example, the method disclosed in the U.S. Published Patent Application No. 2001/0048741, entitled “METHOD OF CALCULATING MULTIPLICATION BY SCALARS ON AN ELLIPTIC CURVE AND APPARATUS USING SAME AND RECORDING MEDIUM” is based upon judging the value of a bit of a scalar value, randomizing the calculation order of addition and doubling operations and then execute the randomized double and add operations. However, this methodology is weak against address-bit attack.
The method disclosed in the U.S. Published Patent Application No. 2003/0059042, entitled “ELLIPTIC SCALAR MULTIPLICATION SYSTEM”, provides scalar multiplication where operations are carried out upon a randomized point in a scalar multiplication method to calculate the scalar-multiplied point from a scalar value and a point on an elliptic curve. Calculating the scalar multiplication may include a step of carrying out an operation upon each bit of the scalar value resulting in a vulnerability to the ABA.
Securing the scalar multiplication algorithm against side channel attacks (SPA and DPA) does not mean protecting the algorithm against address bit attack. Therefore, there is a need for an algorithm with countermeasures against side channel attacks as well as address bit attack.
The ABA attack is based on the correlation between bit values of the scalar, K, and the location (address) of the variables (registers) used in a scalar multiplication algorithm. This type of attack can be based on monitoring operands (source) registers and/or destination registers of ADD and/or DBL operations. Therefore, correlation between accessing source registers and the scalar bit value can occur while reading from these registers. Similarly, correlation between accessing destination registers and the scalar bit value can occur while writing to these registers.
In ADD operations, there is no problem in accessing the source registers, since both operands will be read independently of the scalar bit value. However, in BDL operations, one of the source registers should be selected based on the scalar bit value in order to get the correct result of the scalar multiplication, KP. Therefore, this selection process correlates the scalar bit value to accessing one of these registers, as shown by step 5 in the ML binary algorithm, step 5 in the LM binary algorithm and step 3 in Takagi's algorithm (all given above).
The location of where to store the result of ADD and DBL operations can also be correlated to the scalar bit value as shown by the 2-registers version of Takagi's algorithm, given below:
for i = n−2 downto 0{   Q[1−ki] = ADD (Q[0], Q[1])   Q[ki] = DBL(Q[ki])}.
None of the above inventions, patents and published patent applications, taken either singly or in combination, is seen to describe the instant invention as claimed. Thus, a system and method for performing iterative scalar multiplication which is protected against address bit attack solving the aforementioned problems is desired.